Middle of the linked list

Time: O(N); Space: O(1); easy

Given a non-empty, singly linked list with head node head, return a middle node of linked list.

If there are two middle nodes, return the second middle node.

Example 1:

Input: head = {ListNode} 1->2->3->4->5->None

Output: {ListNode} 3->4->5->null

Explanation:

• Node 3 from this list (Serialization: [3,4,5])

• The returned node has value 3. (The judge’s serialization of this node is [3,4,5]).

• Note that we returned a ListNode object ans, such that:

  • ans.val = 3

  • ans.next.val = 4

  • ans.next.next.val = 5 and

  • ans.next.next.next = None

Example 2:

Input: head = {ListNode} 1->2->3->4->5->6->None

Output: {ListNode} 4->5->6->null

Explanation:

• Node 4 from this list (Serialization: [4,5,6])

• Since the list has two middle nodes with values 3 and 4, we return the second one.

Constraints:

• The number of nodes in the given list will be between 1 and 100.

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

1. Fast and Slow Pointer

Intuition and Algorithm

When traversing the list with a pointer slow, make another pointer fast that traverses twice as fast.

When fast reaches the end of the list, slow must be in the middle.

class Solution1(object):
    """
    Time: O(N)
    Space: O(1)
    """
    def middleNode(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        slow, fast = head, head

        while fast and fast.next:
            slow, fast = slow.next, fast.next.next

        return slow

s = Solution1()

head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)
res = s.middleNode(head)
assert res.val == 3
assert res.next.val == 4
assert res.next.next.val == 5
assert res.next.next.next == None

head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)
head.next.next.next.next.next = ListNode(6)
res = s.middleNode(head)
assert res.val == 4
assert res.next.val == 5
assert res.next.next.val == 6
assert res.next.next.next == None

2. Output to Array [O(N), O(N)]

Intuition and Algorithm

Put every node into an array A in order. Then the middle node is just A[A.length // 2], since we can retrieve each node by index.

class Solution2(object):
    def middleNode(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        A = [head]
        while A[-1].next:
            A.append(A[-1].next)
        return A[len(A) // 2]

s = Solution2()

head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)
res = s.middleNode(head)
assert res.val == 3
assert res.next.val == 4
assert res.next.next.val == 5
assert res.next.next.next == None

head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)
head.next.next.next.next.next = ListNode(6)
res = s.middleNode(head)
assert res.val == 4
assert res.next.val == 5
assert res.next.next.val == 6
assert res.next.next.next == None

See also:

https://leetcode.com/problems/middle-of-the-linked-list

https://www.lintcode.com/problem/middle-of-the-linked-list/description